function update_max(dp: number[][][], i: number, j: number, k: number, val: number): void {
    dp[i][j][k] = Math.max(dp[i][j][k], val);
}

function maxSum(nums: number[], k: number, m: number): number {
    const nums_len = nums.length;
    console.log('nums_len', nums_len);
    const dp = Array.from({length : nums_len+1}, (_, idx) => {
        const inner_arr = Array.from({length: k+1}, () => [Number.MIN_SAFE_INTEGER, Number.MIN_SAFE_INTEGER]);
        return inner_arr;
    });
    // console.log(dp);

    const suffix_sum = Array.from({length : nums_len+1}, (_, idx) => 0);
    // console.log('suffix_sum', suffix_sum);
    for (let i = 1; i <= nums_len; i++)
        suffix_sum[i] = suffix_sum[i-1] + nums[i-1];
    // console.log('nums', nums);
    // console.log('suffix_sum', suffix_sum);
    function get_seg_sum(i: number, j: number) {
        i++, j++;
        return suffix_sum[j] - suffix_sum[i-1];
    }
    function get_seg_after_idx(idx: number, seg_len = m) {
        const res = get_seg_sum(idx+1, idx+m);
        // console.log('get_seg_after_idx', idx, seg_len, res);
        return res;
    }

    for (let i = 0; i < nums.length; i++)
    {
        dp[i][0][0] = 0;
        if (i >= m-1)
            dp[i][1][1] = get_seg_after_idx(i-(m-1)-1);
    }

    // console.log('init:\n', dp);

    for (let j = 0; j <= k; j++)
    {
        let max_jSeg_sum = Number.MIN_SAFE_INTEGER;
        for (let i = 0; i < nums.length; i++)
        {
            // console.log(j, i);
            
            // do nothing, just transfer dp[i][j][0] to dp[i+1][j][0]
            if (max_jSeg_sum != Number.MIN_SAFE_INTEGER)
                update_max(dp, i, j, 0, max_jSeg_sum);
            const cur_max = Math.max(dp[i][j][0], dp[i][j][1])
            // update max_jSeg_sum
            if (cur_max == Number.MIN_SAFE_INTEGER)
                continue;
            max_jSeg_sum = Math.max(max_jSeg_sum, cur_max);

            // add new seg (whose len is at least m)
            if (j+1 <= k && i+m < nums.length)
            {
                const sum_val_addNewSeg = cur_max+get_seg_after_idx(i);
                update_max(dp, i+m, j+1, 1, sum_val_addNewSeg);
                if (i+m+1 < nums.length)
                    update_max(dp, i+m+1, j+1, 0, sum_val_addNewSeg);
            }
            // span last seg
            if (dp[i][j][1] != Number.MIN_SAFE_INTEGER && i+1 < nums.length)
                update_max(dp, i+1, j, 1, dp[i][j][1]+nums[i+1]);
        }
    }

    // console.log('result:\n', dp);

    // return -1;

    let max_ret = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < nums.length; i++)
    {
        max_ret = Math.max(max_ret, dp[i][k][0], dp[i][k][1]);
    }
    return max_ret;
};

/* new plan */
// dp[i:1-n][j:1-k][0-1]：最后一段子数组的结尾下标是不是i]
//      前1-i中 j段子数组 最后一段子数组的结尾下标是不是i 情况下的最大和

// 漏看了一个条件：每个子数组的长度 至少 为 m
// 似乎加上这个条件题会更简单？

// === trans formula
// === 感觉需要改为贡献/后推的方式
// dp[i][j][0/1]得到以后
// dp[i][j][0]+sum(m个)去更新dp[i+m][j+1][1]
// dp[i][j][0]+sum(m个)去更新dp[i+m+1][j+1][0]
// dp[i][j][1]+nums[i+1]去更新dp[i+1][j][1]

// === trans logic/direction
// i, j --> i, j+1

const input_arr = [
    {nums:[1,2,-1,3,3,4], k:2, m: 2},
    {nums:[-10,3,-1,-2], k:4, m: 1},
];
input_arr.forEach(({nums, k, m}) => {
    console.log(nums, k, m);
    console.log('res:\t', maxSum(nums,k, m));
})